package com.leetcode.partition7;

import java.util.Arrays;

/**
 * @author `RKC`
 * @date 2021/9/27 8:48
 */
public class LC639解码方法2 {

    private static final int MOD = 1000000007;

    public static int numDecodings(String s) {
        return dynamicProgramming(s);
    }

    public static void main(String[] args) {
//        String s = "21*";
        String s = "7*9*3*6*3*0*5*4*9*7*3*7*1*8*3*2*0*0*6*";
        System.out.println(numDecodings(s));
    }

    private static int dynamicProgramming(String s) {
        long[] dp = new long[s.length() + 1];
        dp[0] = 1;
        for (int i = 1; i < dp.length; i++) {
            //当前s[0,i-1]有效组合等于s[i-2]的有效组合乘以当前字符能组合成有效字符的次数
            dp[i] = dp[i - 1] * check1Char(s.charAt(i - 1)) % MOD;
            if (i <= 1) continue;
            //当前s[0,i-1]有效组合等于一个字符的组合数+两个字符的组合数，而两个字符的组合数等于s[0,i-3]的有效组合数乘以s[i-1]和s[i-2]的两个有效组合数
            dp[i] = (dp[i] + dp[i - 2] * check2Char(s.charAt(i - 2), s.charAt(i - 1))) % MOD;
        }
        System.out.println(Arrays.toString(dp));
        return (int) (dp[s.length()] % MOD);
    }

    private static int check1Char(char c) {
        if (c == '0') return 0;     //一个字符时的0是无效的
        if (c >= '1' && c <= '9') return 1;
        if (c == '*') return 9;
        return 0;
    }

    private static int check2Char(char a, char b) {
        //两个*号时有15种合法的组合方式
        if (a == '*' && b == '*') return 15;
        //a为*时，当b属于[0, 6]时，a有两种情况 1和2；当b属于[7, 9]时，a只能取1
        if (a == '*' && b >= '0' && b <= '6') return 2;
        if (a == '*' && b >= '7' && b <= '9') return 1;
        //b为*时，当a为1时，b可以取1到9种；当a为2时，b只能有取1到6
        if (b == '*' && a == '1') return 9;
        if (b == '*' && a == '2') return 6;
        //a和b都不为*，只有a不为0且ab组合小于等于26时，才能正确被解码
        if (a != '*' && b != '*' && a != '0' && (a - '0') * 10 + (b - '0') <= 26) return 1;
        else return 0;
    }
}
